

#题目：匹配给定的字符串  给出：FDA ，匹配 ABACFDA
def build_next (patt):
    next=[0]      #定义一个next
    prefix_len = 0 #定义一个共同长度
    i = 1
    while i < len(patt):
        if patt[prefix_len] == patt[i]:
            prefix_len +=1
            next.append(prefix_len)
            i +=1
            print('next', next)
        else:
            if (prefix_len == 0):
                next.append(0)
                i +=1
            else:
                prefix_len = next[prefix_len - 1]
                print('prefix_len',prefix_len)
        return  next

def KmpTest(String,patt):
    next = build_next(patt) #假设next数组

    i = 0  #主串
    j = 0  #子串
    while i <len(String):
        if String[i] == patt[j]:       #字符匹配，指针后移
            i +=1
            j +=1
            print('i',i)
            print('j',j)
        elif j > 0:       #
            j = next[j - 1]
        else:
             i  += 1
        if j == len(patt):
             return   i - j

